package sort;

/**
 * 插入排序，时间复杂度最坏N^2,最好N
 */
public class InsertSort {
    public static <E extends Comparable<E>> void sort(E[] array) {
        for (int i = 1; i < array.length; i++) {
            int k = i;
            E tmp = array[i];
            for (int j = i - 1; j >= 0 && tmp.compareTo(array[j]) < 0; j--) {
                array[j + 1] = array[j];
                k = j;
            }
            array[k] = tmp;
        }
    }
}